# -*- coding: iso-8859-2 -*-

import numpy
import mlpy

import math

from authorshipanalyzer.utils import sortDictionaryByValue
from authorshipanalyzer.utils import combinationNum

class SVM:
    '''
    Class classifying elements
    '''
    
    def __init__(self, treshold = 0.8, kernel='linear', kp=0.10000000000000001, C=1.0, tol=0.001, eps=0.001, maxloops=1000, cost=0.0):
        '''
        kernel    - 'linear', 'gaussian', 'polynomial', 'tr'
        kp        - kernel parameter (two sigma squared) for gaussian and polynomial kernel
        C         - regularization parameter
        tol       - tolerance for testing KKT conditions
        eps       - convergence parameter
        maxloops  - maximum number of optimization loops
        cost      - for cost-sensitive classification [-1.0, 1.0]
        '''
        self.classifier = mlpy.svm(kernel, kp, C, tol, eps, maxloops, cost)  
        self.treshold = treshold
    
    def binClassify(self, vectors, vector):
        '''
        @param vector: vector to classify
        @param vectors: two vectors of features of separate classes
        @return index of vector which was closer
        '''
        self.classifier.compute(numpy.array(vectors), numpy.array([1, 2]))             # compute svm
        return self.classifier.predict(numpy.array(vector)) - 1               # predict svm model on test point

    def recursiveClassify(self, dicts, classSize = 3):
        '''
        Split dicst into smaller parts and cluster each part. Cluster
        until not changed.
        '''
        sizeDicts = len(dicts)
        if sizeDicts < classSize:
            return self.classify(dicts)
        
        dictParts = []
        partNum = int(math.ceil(float(len(dicts)) / float(classSize)))
#        print partNum
        for i in range(partNum):
            dictParts.append(dicts[i * classSize : i * classSize + classSize])
            
        if len(dictParts[-1]) < 3:
            dictParts[-2].extend(dictParts[-1])
            del dictParts[-1]
            partNum -= 1
            
        groups = []
        for dictPart in dictParts:
            groups.extend(self.classify(dictPart))
            
        if len(groups) < len(dicts):
            return self.recursiveClassify(groups, classSize)
        
        print "!!!!!!!!!!!!!!!!!! " + str(len(groups))
        return self.classify(groups) #groups    
         
        
#        print dictParts 
#        groups
#        beforeLenGroups = len(dicts)   
#        while len(groups) > beforeLenGroups:
#            beforeLenGroups = 0
#            groups = []
#            for i in range(partNum):
#                groupsPart = self.classify(dictParts[i])
#                groups.extend(groupsPart)
#
#            beforeLenGroups = len(groups)
#            dictParts = groups

    def classify(self, dicts):
        '''
        @param vectors: list of dicts with features <feature, value> f.e. <word, freqency> 
        @return: list of indexes of the closest dict or -1
        '''
        size = len(dicts)
        
        voteArray = self.zeros(size)
        
        if size < 3:
            return dicts
        
        quantVal = 1.0 / float(size - 2) #1.0 / float(combinationNum(size - 1, 2)) * (size - 1)
        
        for i in range(size):
            pairs = self.generatePairs(size, i)
            for pair in pairs:
                # create feature vectors
                v1, v2, v3 = self.createVectors(dicts[pair[0]], dicts[pair[1]], dicts[i])
                
                # find the more similar class for v3 in comparison to v1 and v2
                index = self.binClassify([v1, v2], v3)
                
                # increment vote array with result
                voteArray[i][pair[index]] += quantVal #100.0 / float(len(pairs))
                
         
        self.printVoteArray(voteArray)
        
        clusters = self.cluster(voteArray)
        print clusters
        
        groups = self.extractKeyWords(dicts, clusters)
        
#        for group in groups:
#            print " GROUP ==========================="
#            items = sortDictionaryByValue(group)
#            for item in items:
#                print item[0] + " ---> " + str(item[1])
                
        return groups
#        print
#        print
#        self.printSummedVotedArray(voteArray)
     
     
    def createClustersKeyWordsList(self, clusters):
        result = {}
        for label, dicts in clusters.items():
            result[label] = self.createClusterKeyWordsList(dicts)
        return result
     
    def createClusterKeyWordsList(self, dicts):
        result = {}
        for dict in dicts:
            for word, freq in dict.items():
                if result.has_key(word):
                    result[word] += freq
                else:
                    result[word] = freq
        return result
     
    def extractKeyWords(self, dicts, clusters):
        '''
        @return list of dicts<word, frequency> for each cluster 
        '''
        groups = []
        
        for cluster in clusters:
            keyWords = {}
            for index in cluster:
                dict = dicts[index]
                for word, freq in dict.items():
                    if keyWords.has_key(word):
                        keyWords[word] += freq
                    else:
                         keyWords[word] = freq
            groups.append(keyWords)
            
        return groups
     
    def cluster(self, voteArray):
        '''
        @return: list of lists of indexes with clustered points;
        each list is a one cluster with indexes
        '''     
        maxList = []
        size = len(voteArray)
        
        # create pairs of indexes with the highest similarity
        # TODO when join? treshold? symmetric sum?
       #treshold = 0.7 #tresholdMult * 100 / float(size)
        print "Treshold set to: " + str(self.treshold)
        for i in voteArray.keys():
            maxVal = 0.0
            maxI = -1
            for j in voteArray.keys():
                val = voteArray[i][j] + voteArray[j][i]
                if val > maxVal and voteArray[i][j] > self.treshold and voteArray[j][i] > self.treshold:
                    maxVal = val
                    maxI = j
                    
            if maxI != -1:
                maxList.append([i, maxI])
            else:
                maxList.append([i])
          
        result = []
        while len(maxList) > 0:
            
            cluster = set(maxList[0])
            del maxList[0]

            change = True
            while change and len(maxList) > 0:
                change = False
                for i in range(0, len(maxList)):
                    intersection = cluster.intersection(set(maxList[i]))
                    if len(intersection) > 0:
                        cluster.update(set(maxList[i]))
                        del maxList[i]
                        change = True
                        break
            result.append(list(cluster))   
            
        return result   

     
    def printSummedVotedArray(self, voteArray):
        '''
        Print vote array to stdout
        '''
        size = len(voteArray)
        result = self.zeros(size)
        
        for i in range(size):
            for j in range(size):
                result[i][j] = voteArray[i][j] + voteArray[j][i]
                
        self.printVoteArray(result)
     
    def printVoteArray(self, voteArray): 
        '''
        Print vote array to stdout
        '''
        
        size = len(voteArray)
        
        print "\t",        
        for i in voteArray.keys():
            print str(i) + "\t",
        print
                
        for i in voteArray.keys():
            print str(i) + "\t",
            max = 0.0
            for j in voteArray.keys():
                if voteArray[i][j] > max:
                    max = voteArray[i][j]
                    
            for j in voteArray.keys():
                if voteArray[i][j] != max:
                    print " %4.3f \t" % voteArray[i][j],
                else:
                    print ">%4.3f<\t" % voteArray[i][j],
            print "" 
            
    def zeros(self, labels):
        result = {}
        for l1 in labels:
            row = {}
            for l2 in labels:
                row[l2] = 0.0
            result[l1] = row
        return result
        
                
    def createVectors(self, d1, d2, d3):
        '''
        Create feature vectors from dictionaries
        '''
        
        listOfPatterns = []
        listOfPatterns.extend(d1.keys())
        listOfPatterns.extend(d2.keys())
        listOfPatterns.extend(d3.keys())
        
        patterns = list(set(listOfPatterns))

        v1 = []
        v2 = []
        v3 = []
                
        for pattern in patterns:
            for dv in [ [d1, v1], [d2, v2], [d3, v3] ]:
                if dv[0].has_key(pattern):
                    dv[1].append(dv[0][pattern])
                else:
                    dv[1].append(0.0)

        return v1, v2, v3
                
    def generatePairs(self, values, exclude):
        result = []
        
        for i in range(len(values)):
            v1 = values[i]
            if v1 == exclude:
                continue
            for j in range(i + 1, len(values)):
                v2 = values[j]
                if v2 == exclude:
                    continue
                
                result.append([v1, v2])
                
        return result
    
    ######################
    
    def preprocess(self, dicts, borderFreq):
        '''
        Create vector model. Remove words which occour less then borderFreq,
        count weights.
        '''
        
        # approximations, some messages may not contain any key word
        N = float(len(dicts))  
        
        # Create frequency of occourences of all words
        allWords = {}
        for dict in dicts:
            for word, freq in dict.items():
                if allWords.has_key(word):
                    allWords[word] += freq
                else:
                    allWords[word] = freq
        
        # Remove words which occours less then borderFreq times
        for word, freq in allWords.items():
            if freq < borderFreq:
                allWords.pop(word)
            else:
                allWords[word] = math.log(N / float(freq))    

#        for word, freq in allWords.items():
#            print word + " " + str(freq)

        resultDicts = []
        for dict in dicts:
            resDict = {}
            for word, freq in dict.items():
                if allWords.has_key(word):
                    resDict[word] = freq * allWords[word]
            resultDicts.append(resDict)
        
        dicts = None
        dicts = resultDicts
    
    
    def clusterize(self, dicts, classSize, borderFrequency, similarity):
        '''
        @param dicts: list of dicts with word frequencies
        @return: list of labels
        '''
        
        # Create cluster dict where each cluster is associated with
        # index of the dict and it contains indexes of similar messages
        self.preprocess(dicts, borderFrequency)
        
        size = len(dicts)
        
        labels = []
        for i in range(size):
            labels.append(i)
        
        classBorders = []
        
        gap = 0
        while gap < size:
            classBorders.append(gap)
            gap += classSize
            
        if size - classBorders[-1] > 3:
             classBorders.append(size)
        else:
            classBorders[-1] += size - classBorders[-1]
            
        print classBorders
        
        clusters  = {}
        for i in range(len(dicts)):
            for j in range(1, len(classBorders)):
                fromB = classBorders[j - 1]
                toB = classBorders[j]
                
                if clusters.has_key(i):
                    clusters[i].extend(self.getSimilar(dicts, labels[fromB:toB], i, similarity))
                else:
                    clusters[i] = self.getSimilar(dicts, labels[fromB:toB], i, similarity)  
        
        return clusters
        
        
    def getSimilar(self, dicts, labels, patternIndex, similarity):
        '''
        @dicts: list of dictionaries which similiarity is recognized
        @patternIndex: index of message which similarity is recognized
        @similarity: the float border of similarity [0;1.0]
        @return: list of indexes of similar messages
        '''
        
        print str(patternIndex) + " ? " + str(labels)
        
        voteArray = {}
        for label in labels:
            voteArray[label] = 0.0
                
        pairs = self.generatePairs(labels, patternIndex)
        quantVal = 1.0 / float(len(labels) - 1) 
        for pair in pairs:
            # create feature vectors
            v1, v2, v3 = self.createVectors(dicts[pair[0]], dicts[pair[1]], dicts[patternIndex])
            
            # find the more similar class for v3 in comparison to v1 and v2
            index = self.binClassify([v1, v2], v3)
            print str(pair) + " ==== " + str(index)
#            print str(patternIndex) + " " + str(pair) + " --> " + str(index)
            if index == -1:
                continue
            # increment vote array with result
            voteArray[pair[index]] += quantVal
            
        print voteArray 
        
        similarities = []
        for label, votes in voteArray.items():
            if votes > similarity:
                similarities.append(label)
        
        return similarities

    def clusterize2(self, dicts, classSize = 20):
        '''
        @param dicts: list of dicts with word frequencies
        @return: list of labels
        '''
        
        self.preprocess(dicts, 3)
        
        labels = range(1, len(dicts) + 1)
        # <label, list<dicts>>
        clusterDicts = {}
        for i in range(len(dicts)):
            if clusterDicts.has_key(labels[i]):
                clusterDicts.append(dicts[i])
            else:
                clusterDicts[labels[i]] = [dicts[i]]
        
        clusterNum = len(clusterDicts)
        
        changed = True
        while clusterNum > classSize + 3 and changed:
            changed = False
            
            dictParts = []
            partNum = int(math.ceil(float(clusterNum) / float(classSize)))
#            print partNum
            
            i = 0
            labels = []
            for label in clusterDicts.keys():
                labels.append(label)
                
                i += 1
                if i == classSize:
                    dictParts.append(labels)
                    labels = []
                    i = 0
                    
            if labels != []:
                dictParts.append(labels)
                    
#            print "l " + str(dictParts)  
            if len(dictParts) < 3:
                break
                          
            if len(dictParts[-1]) < 3:
                dictParts[-2].extend(dictParts[-1])
                del dictParts[-1]
                partNum -= 1
                
            groups = {}
            for dictPart in dictParts:
                clusterDictPart = {}
                for label, cluster in clusterDicts.items():
                    if label in dictPart:
                        clusterDictPart[label] = clusterDicts[label]
                groups.update(self.classify2(clusterDictPart))
            
            if len(groups) != len(clusterDicts):
                changed = True
                clusterDicts = groups        
     
        return self.classify2(clusterDicts)
    
    def classify2(self, clusterDicts):
        '''
        '''
                
        size = len(clusterDicts)
        voteArray = self.zeros(clusterDicts.keys())
        
        if size < 3:
            return clusterDicts
        
        quantVal = 1.0 / float(size - 2)
        
        for label in clusterDicts.keys():
            pairs = self.generatePairs(clusterDicts.keys(), label)
            for pair in pairs:
                # create feature vectors
                vectors = self.createVectors2(clusterDicts[pair[0]], clusterDicts[pair[1]], clusterDicts[label])
                
                # find the more similar class for v3 in comparison to v1 and v2
                index = self.binClassify2(vectors, pair)
                
#                print str(label) + " " + str(pair) + " --> " + str(index)
                if index == 0:
                    continue
                
#                print str(label) + " " + str(index)
                # increment vote array with result
                voteArray[label][index] += quantVal #100.0 / float(len(pairs))
                
         
        self.printVoteArray(voteArray)
        
        clusters = self.cluster(voteArray)
#        print clusters
        for cluster in clusters:
            if len(cluster) > 1:
                mainCluster = cluster[0]
                for index in cluster[1:]:
#                    print index
#                    print clusterDicts
                    clusterDicts[mainCluster].extend(clusterDicts[index])
                    del clusterDicts[index]
                    
        return clusterDicts
                   
                
    def binClassify2(self, vectors, labels):
        '''
        @param vectors:
        vectors[0], vectors[1] - opponent clusters
        vector[2] - assigned cluster
        @param labels: 
        labels[0] - label of vector[0]
        labels[1] - label of vector[1]
        '''
        
        trainVectors = []
        trainLabels = []
        
        for i in [0, 1]:
            for v in vectors[i]:
                trainVectors.append(v)
                trainLabels.append(labels[i])
            
        self.classifier.compute(numpy.array(trainVectors), numpy.array(trainLabels))             # compute svm
        return self.classifier.predict(numpy.array(vectors[2]))[0]               # predict svm model on test point
    
        
    def createVectors2(self, d1, d2, d3):
        '''
        @param d1, d2, d3: lists of dicts with word frequencies
        @return: list of vectors of features
        '''
        # list of words occouring in any of the dicts
        listOfPatterns = []
        for ld in [d1, d2, d3]:
            for d in ld:
                listOfPatterns.extend(d.keys())
        
        patterns = list(set(listOfPatterns))

        v1 = []
        v2 = []
        v3 = []
                
        for dlv in [ [d1, v1], [d2, v2], [d3, v3] ]:
            for d in dlv[0]:
                subv = []
                for pattern in patterns:
                    if d.has_key(pattern):
                        subv.append(d[pattern])
                    else:
                        subv.append(0.0) 
                dlv[1].append(subv)

        return v1, v2, v3
            
        
    
    
if __name__ == "__main__":
    svm = SVM(0.8)
#    print svm.generatePairs([1,2,3,4], 2)
    
    d1 = { 'a' : 2, 'b' : 3, 'c' : 4 }
    d2 = { 'a' : 3, 'b' : 3, 'd' : 3 }
    d3 = { 'b' : 1, 'c' : 4, 'f' : 4 }
    
    d4 = { 'b' : 1, 'c' : 4, 'f' : 9 }
    d5 = { 'a' : 2, 'b' : 3, 'c' : 4 }
    d6 = { 'a' : 3, 'b' : 3, 'd' : 3 }
    d7 = { 'b' : 1, 'c' : 4, 'f' : 4 }
    d8 = { 'b' : 1, 'c' : 4, 'd' : 9 }
    
    dicts = [ d1, d2, d3, d4, d5, d6, d7, d8 ]
    
    clustDicts = {}
    clustDicts[0] = [d1, d2]
    clustDicts[1] = [d3, d4, d5]
    clustDicts[2] = [d2, d3]
     
#    vs = svm.createVectors2(clustDicts[0], clustDicts[1], clustDicts[2])
#    print vs
#    
#    print svm.binClassify2(vs, [4,5])
#    for v in vs:
#        for val in v:
#            print str(v), " "
#        print
    
#    print svm.createVectors(d1, d2, d3)
#    svm.classify(dicts)
    
#    groups = svm.recursiveClassify(dicts, 3)
#    print groups
    
    clusters = svm.clusterize(dicts, 4, 3, 0.7)
    for key, value in clusters.items():
        print str(key) + " --> " + str(value)
    print clusters.keys()
    
    from sys import exit
#    exit(0)
        
#########################

    import datetime
    import os
    
    from authorshipanalyzer.message import Message
    from authorshipanalyzer.message import MessageReader
    from authorshipanalyzer.file import Path
    from authorshipanalyzer.textmodifier import MessagePreprocessor
    from authorshipanalyzer.slot import Slot
    from authorshipanalyzer.slot import SlotManager
    
    fromDate = datetime.date(2008,4, 1)
    toDate = datetime.date(2008, 5, 3)
    
    mr = MessageReader(Path.getMainDir() + os.sep + "info1")
    messages = mr.readMessages(fromDate, toDate)
#    messages = MessagePreprocessor().preprocess(messages)
    
    from time import time
    
    start = time()
    sm = SlotManager()
    sm.createSlots(messages)
    end = time()
    
    print "Creating slots: " + str(end - start) + " seconds"
    print "Number of messages:", str(len(messages))
    
    import copy
    from authorshipanalyzer.file import ResourceReader
    from authorshipanalyzer.file import Path

    file = open("/tmp/message.txt", "w")
#    functionWords = ResourceReader().readWordList(Path.getResourceDir() + os.sep + "functionWords.txt")
    dicts = []
    i = 0
    for slot in sm.getSlots():
        d = copy.deepcopy(slot.contentWordFrequency)
#        for k in d.keys():
#           if k in functionWords:
#               del d[k] 
            
        dicts.append(d)
        
        file.write(str(i) + "\n")
        file.write(slot.message.getText())
        file.write("\n\n\n")
        
        i += 1
        
    file.close()
        
    svm = SVM(0.99, 'polynomial')
#    clusters = svm.clusterize(dicts, 30, 5, 0.95) # dicts, classSize, borderFrequency, similarity
#    for key, value in clusters.items():
#        print str(key) + " --> " + str(value)
#    print clusters.keys()
    
#    svm.classify(dicts)
#    clusters = svm.recursiveClassify(dicts, 20)
    
    clusters = svm.clusterize2(dicts, 20)
    print clusters
    print clusters.keys()
#    
    from nltk.cluster.util import cosine_distance
    
#    from authorshipanalyzer.utils import sortDictionaryByValue 
#    for cluster in clusters:
#        for item in sortDictionaryByValue(cluster):
#            if item[1] > 1.0:
#                print item[0] + " ---> " + str(item[1])
#        print "------------------"
    
    
    categories = svm.createClustersKeyWordsList(clusters)
        
    slots = sm.getSlots()
    for j in range(len(slots)):
        slot = slots[j]
        maxVal = 0.0
        maxI = -1
        for label, dict in categories.items():
            slotVector, clusterVector, _trash = svm.createVectors(slot.contentWordFrequency, dict, {})
            val = cosine_distance(slotVector, clusterVector)
#            print str(j) + " -- cluster --> " + str(i) + " with " + str(val)
            if val > maxVal:
                maxVal = val
                maxI = label
        print str(j) + " -- cluster --> " + str(maxI) + " with " + str(maxVal)
    
        
#    print "\n"
#    i = 0
#    for cluster1 in clusters:
#        j = 0
#        for cluster2 in clusters:
#            v1, v2, _trash = svm.createVectors(cluster1, cluster2, {})
#            val = cosine_distance(v1, v2)
#            print str(i) + " --- " + str(j) + " = " + str(val)
#            j += 1
#        i += 1 
        